#include <stdio.h>

void PrintArray(int * a,int size)
{
    for(int i = 0;i < size;i++)
        printf("%d ",a[i]);
    printf("\n");
}

void Swap(int *a,int *b)
{
    int temp = *a;
    *a = *b;
    *b =temp;
}

//冒泡
void BubbleSort(int *a,int size)//O(n^2)
{
    for(int i = 0;i < size - 1;i++)//将n个数归位
    { 
        int falg = 0;
        for(int j = 0;j < size - 1 - i;j++)//两两比较
        {
            if(a[j] > a[j + 1])
            {
                Swap(&a[j],&a[j+1]);
                falg = 1;
            }
        }
        if(falg == 0)//数列有序
            break;
    }
}

//插入
void InsertSort(int *a,int size)
{
    for(int i = 1;i < size;i++)
    {
        int j = i;//即将要插入的数
        int temp = a[j];
        for(;j > 0;j--)
        {
            if(a[j - 1] > temp)//前面的数比我大
            {
                a[j] = a[j-1];
            }
            else//前面数比我大
            {
                break;
            }
        }
        a[j] = temp;
    }
}

//选择排序
void ChooseSort(int *a,int size)
{
    for(int i = 0;i < size - 1;i++)
    {
        int min = i;
        for (int j = i + 1; j < size; j++)
        {
            if(a[min] > a[j])
            {
                min = j;
            }
        }
        Swap(&a[min],&a[i]);
    }
}

//双指针
void ChooseSort2(int *a,int size)
{
    int left = 0;
    int right = size - 1;
    while(left < right)
    {
        int min = left;
        int max = right;
        for(int i = left;i <= right;i++)
        {
            if(a[i] < a[min])
                min = i;
            if(a[i] > a[max])
                max = i;
        }
        Swap(&a[left],&a[min]);
        if(max == left)
        {
            max = min;
        }
        Swap(&a[right],&a[max]);//极值在两边有问题
        left++;
        right--;
    }
}

//快速排序  双指针 分治
void FastSort(int *a ,int start,int end)
{
    if(start >= end)
        return;
    int left = start;
    int right = end;
    int temp = a[start];
    while(left < right)
    {
        //从右往左找比基准值小的
        while(a[right] > temp && left < right)
            right--;
        if(left < right)
            a[left++] = a[right];//把比基准值小的数放左边
        while(a[left] < temp && left < right)
            left++;
        if(left < right)
            a[right--] = a[left];//把比基准值大的数放右边
    }
    a[left] = temp;

    FastSort(a,start,left-1);
    FastSort(a,right+1,end);
}

int BinarySearch(int *a,int size,int element)
{
    int left = 0;
    int right = size -1;
    while(left <= right)
    {
        int mid = left + (right - left)/2;//((left & right) + (left ^ right)) >> 2
        if(a[mid] == element)
            return mid;
        else if(a[mid] > element)
            right = mid - 1;
        else if(a[mid] < element)
            left = mid + 1;
    }
    return -1;
}

int main()
{
    int a[] = {-1,-2,-3};
    int size = sizeof(a)/sizeof(a[0]);
    //BubbleSort(a,size);
    InsertSort(a,size);
    //FastSort(a,0,size-1);
    PrintArray(a,size);
    // int index = BinarySearch(a,size,32);
    // if(index == -1)
    //     printf("没有找到\n");
    // else
    //     printf("找到了：在第%d个位置\n",index);

    return 0;
}